package ch10;

import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

public class Ch10_7 {
	class Wrapper {
		private int totalHeight;
		private List<Integer> tower;
		
		public Wrapper() {
			totalHeight = 0;
			tower = new LinkedList<Integer>();
		}
		
		public Wrapper add(int index, int height) {
			tower.add(index);
			totalHeight += height;
			return this;
		}
		
		public Wrapper addAll(Wrapper r) {
			tower.addAll(r.tower);
			this.totalHeight += r.totalHeight;
			return this;
		}
		
		public int getHeight() {
			return totalHeight;
		}
		
		public List<Integer> getList() {
			return tower;
		}
	}
	
	private void quickSort(int H[], int W[], int p, int r) {
		if (p < r) {
			int q = partition(H, W, p, r);
			quickSort(H, W, p, q - 1);
			quickSort(H, W, q + 1, r);
		}
	}
	
	private int partition(int H[], int W[], int p, int r) {
		int x = H[r];
		int i = p - 1;
		for (int j = p; j < r; j++) {
			if (H[j] <= x) {
				i = i + 1;
				swap(H, W, i, j);
			}
		}
		swap(H, W, i + 1, r);
		return i + 1;
	}
	
	private void swap(int[] H, int[] W, int i, int j) {
		int tmp = H[i];
		H[i] = H[j];
		H[j] = tmp;
		tmp = W[i];
		W[i] = W[j];
		W[j] = tmp;
	}
	
	public Wrapper solve(int H[], int W[]) {
		quickSort(H, W, 0, H.length - 1);
		Map<Integer, Wrapper> map = new HashMap<Integer, Ch10_7.Wrapper>();
		map.put(0, new Wrapper().add(0, H[0]));
		for (int i = 1; i < H.length; i++) {
			Wrapper wrapper = new Wrapper();
			int above = -1;
			int height = H[i];
			for (int j = 0; j < i; j++) {
				Wrapper r = map.get(j);
				if (r.getHeight() + H[i] > height) {
					if (H[j] < H[i] && W[j] < W[i]) {
						height = r.getHeight() + H[i];
						above = j;
					}
				}
			}
			if (above != -1) {
				wrapper.addAll(map.get(above));
			}
			wrapper.add(i, H[i]);
			map.put(i, wrapper);
		}
		Wrapper result = null;
		for(int i = 0; i < H.length; i++) {
			Wrapper iter = map.get(i);
			if (result == null) {
				result = iter;
			} else if (result.getHeight() < iter.getHeight()) {
				result = iter;
			}
		}
		return result;
	}
	
	public static void main(String[] args) {
		Ch10_7 test = new Ch10_7();
		int[] H = {65, 70, 56, 75, 60, 68};
		int[] W = {100, 150, 90, 190, 95, 110};
		Wrapper result = test.solve(H, W);
		System.out.println(result.getHeight());
		List<Integer> list = result.getList();
		for (Iterator<Integer> iter = list.iterator(); iter.hasNext(); ) {
			int i = iter.next();
			System.out.print("(" + H[i] + ", " + W[i] + ")");
			if (iter.hasNext()) {
				System.out.print(", ");
			}
		}
	}
}
